#include <stdio.h>

/*
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 * 示例 1：
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 *   输出：6
 *   解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 *
 *示例 2：
 *  输入：height = [4,2,0,3,2,5]
 *  输出：9
 */
int trap(int *height, int heightSize)
{
    int i, ret = 0;
    int maxValue = 0, secondMaxValue = 0, *maxValueFirstPos = NULL, *maxValueLastPos = NULL;
    int *leftPtr = NULL, *rightPtr = NULL;
    if (heightSize <= 2)
    {
        return 0;
    }
_retry:
    leftPtr = height;
    rightPtr = height + heightSize - 1;
    // 找到最大值和次大值
    for (i = 0; i < heightSize; i++)
    {
        if (height[i] > secondMaxValue)
        {
            if (height[i] > maxValue)
            {
                secondMaxValue = maxValue;
                maxValue = height[i];
            }
            else
            {
                secondMaxValue = height[i];
            }
        }
    }
    // 利用双指针找到最大值的第一个位置和最后一个位置。
    while (leftPtr < rightPtr)
    {
        if (*leftPtr == maxValue)
        {
            maxValueFirstPos = leftPtr;
            break;
        }
        leftPtr++;
    }
    while (leftPtr < rightPtr)
    {
        if (*rightPtr == maxValue)
        {
            maxValueLastPos = rightPtr;
            break;
        }
        rightPtr--;
    }

    // 当只存在一个最大值时，将次最大值改为次大值。
    if (leftPtr == rightPtr)
    {
        (*leftPtr) = secondMaxValue;
        maxValue = 0;
        secondMaxValue = 0;
        goto _retry;
    }

    // 将整个数组切成三部分，【start~第一个最大值】、【第一个最大值~最后一个最大值】、【最后一个最大值~end】。
    // 【第一个最大值~最后一个最大值】这部分可以直接计算了，其余两部分走递归。
    // 计算【第一个最大值~最后一个最大值】的蓄水量
    leftPtr++;
    while (leftPtr < rightPtr)
    {
        ret += (maxValue - *leftPtr);
        leftPtr++;
    }
    return ret + trap(height, maxValueFirstPos - height + 1) + trap(maxValueLastPos, height + heightSize - maxValueLastPos);
}

int trap2(int *height,int heightSize)
{
    int left = 0;
    int right = heightSize - 1;
    int leftMax = 0;
    int rightMax = 0;
    int result = 0;

    while (left < right)
    {
        if (height[left] < height[right])
        {
            if (height[left] > leftMax)
            {
                leftMax = height[left];
            }
            else
            {
                result += leftMax - height[left];
            }
            left++;
        }
        else
        {
            if (height[right] > rightMax)
            {
                rightMax = height[right];
            }
            else
            {
                result += rightMax - height[right];
            }
            right--;
        }
    }

    return result;
}

int main()
{
    int height[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    int heightSize = sizeof(height) / sizeof(height[0]);
    // int height[] = {4,2,0,3,2,5};
    // int heightSize = sizeof(height) / sizeof(height[0]);
    printf("%d\n", trap2(height, heightSize));
    return 0;
}